 // 1、无头单向非循环链表实现
 public class SingleLinkedList {
    //节点的内部类
     static class ListNode{
         public int val;
         public ListNode next;

         public ListNode(int val){
             this.val = val;
         }
    }
    public ListNode head;

     public void createList(){
         ListNode node1 = new ListNode(12);
         ListNode node2 = new ListNode(23);
         ListNode node3 = new ListNode(34);
         ListNode node4 = new ListNode(45);
         ListNode node5 = new ListNode(56);

         node1.next = node2;
         node2.next = node3;
         node3.next = node4;
         node4.next = node5;

         this.head = node1;
     }
     //头插法
     public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }

     }
     //尾插法
     public void addLast(int data){
         ListNode node = new ListNode(data);
         if(this.head == null){
             this.head = node;
         }else {
             ListNode cur = this.head;
             while (cur.next != null){
                 cur = cur.next;
             }
             //cur指向了最后一个节点
             cur.next = node;
         }
     }
     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index, int data) throws IndexIllegality{
         if(index <0 || index >size()){
             //抛异常
             throw new IndexIllegality("index位置不合法"+index);
         }
         if(index == 0){
             //头插法
             addFirst(data);
             return;
         }
         if(index == size()){
             addLast(data);
             return;
         }
         ListNode node = new ListNode(data);
         ListNode cur = searchPre(index);
         node.next = cur.next;
         cur.next = node;
     }
     //找到index的前一个节点
     private ListNode searchPre(int index){
         ListNode cur = this.head;
         int count = 0;
         while (count != index-1){
             cur = cur.next;
             count++;
         }
         return cur;
     }
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
        ListNode cur = this.head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
         return false;

     }
     //删除第一次出现关键字为key的节点
     public void remove(int key){
         if(this.head == null){
             return;
         }
         if(this.head.val == key){
             this.head = this.head.next;
             return;
         }
         //1.找到前驱
         ListNode cur = findPre(key);
         //2.判断返回值是否为空
         if(cur == null){
             System.out.println("没有你要删除的数字");
             return;
         }
         //删除
         ListNode del = cur.next;
         cur.next = del.next;
     }
     //找到key的前一个节点
     private ListNode findPre(int key){
         ListNode cur = this.head;
         while (cur.next != null){
           if(cur.next.val == key){
               return cur;
           }
           cur = cur.next;
         }
         return null;
     }
     //删除所有值为key的节点
     public void removeAllKey(int key){
         if(this.head == null){
             return;
         }
         ListNode prev = head;
         ListNode cur = head.next;
         while (cur != null){
             if(cur.val == key){
                 prev.next = cur.next;
                 cur = cur.next;
             }else {
                 prev = cur;
                 cur = cur.next;
             }
         }
         if(head.val == key){
             head = head.next;
         }
     }

     //得到单链表的长度
     public int size(){
         int count = 0;
         ListNode cur = this.head;
         while (cur != null){
             count++;
             cur = cur.next;
         }
         return count;
     }
     public void display(){
        ListNode cur = this.head;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;

        }
         System.out.println();
     }
     public void clear(){
        ListNode cur = this.head;
        while (cur != null){
            ListNode curNext = cur.next;

           // cur.val = null;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;
     }
 }